#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:

    // 209. 长度最小的子数组
    // https://leetcode.cn/problems/minimum-size-subarray-sum/
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int sum = 0;
        int len = INT_MAX;
        while (right < nums.size())
        {
            sum += nums[right];
            while (sum >= target)
            {
                len = min(len, right - left + 1);
                sum -= nums[left++];
            }
            ++right;
        }
        if (len == INT_MAX)
        {
            return 0;
        }
        else 
        {
            return len;
        }
    }

    // 3. 无重复字符的最长子串
    // https://leetcode.cn/problems/longest-substring-without-repeating-characters/
    // int lengthOfLongestSubstring(string str) {
    //     if (str.size() == 0)
    //     {
    //         return 0;
    //     }

    //     int left = 0, right = 0;
    //     int len = 0;
    //     unordered_set<char> hash;
    //     while (right < str.size())
    //     {

    //         while ( right < str.size() && hash.find(str[right]) == hash.end() )
    //         {
    //             hash.insert(str[right++]);
    //         }
    //         len = max(len, right - left);

    //         while (str[left] != str[right])
    //         {
    //             hash.erase(str[left++]);
    //         }
    //         hash.erase(str[left++]);
    //     }
    //     return len;
    // }
    int lengthOfLongestSubstring(string str) {
        if (str.size() == 0)
        {
            return 0;
        }

        int left = 0, right = 0;
        int len = 0;
        int hash [128] = { 0 };
        
        while (right < str.size())
        {
            hash[str[right]]++;
            while (hash[str[right]] > 1)
            {
                --hash[str[left++]];
            }
            len = max(len, right - left + 1);
            ++right;
        }

        return len;
    }

    // 1004. 最大连续1的个数 III
    // https://leetcode.cn/problems/max-consecutive-ones-iii/
    int longestOnes(vector<int>& nums, int k) {
        int OneLen = 0;
        int left = 0, right = 0;
        int zero = 0;
        while (right < nums.size())
        {
            if (nums[right] == 0) ++zero;
            while (zero > k)
            {
                if (nums[left] == 0) --zero;
                ++left;
            }
            OneLen = max(OneLen, right - left + 1);
            ++right;
        }
        return OneLen;
    }
};